1. Field of the Invention
The present invention relates to garbage collection, and more particularly, to adaptive garbage collection using an adaptive asymmetric space structure in which the position of a space boundary changes in the structure of a semi-space copying collection algorithm.
2. Description of the Related Art
Garbage, in terms of programming, is data memory space that is determined as being occupied by an object no longer referenced by a program and then collected by an operating system. Garbage collection is a process of freeing such memory space so that the memory space can be efficiently recycled for other programs. In other words, garbage collection is a method for dynamically managing memory.
Conventionally, an operating system may forcibly terminate a program that fails to return memory space occupied by an object no longer referenced by the program when necessary, but usually, programmers need to clearly declare necessary memory space and make a program returning the memory space to the operating system when the memory space is no longer needed by the program.
When return of the no-longer needed memory space is neglected, the program may stop by unknown causes rather than by a logical bug. It is very difficult for programmers to chase down an elusive problem. Accordingly, garbage collection techniques of automatically finding memory space that is not used within a system and freeing the memory space have been developed.
Algorithms for garbage collection include a semi-space copying collection algorithm and a generational garbage collection algorithm. The following description concerns these two algorithms.
FIG. 1 illustrates a conventional semi-space copying collection algorithm.
As shown in FIG. 1, a memory area is divided into two areas of equal space, from-space and to-space. The from-space is a portion of the memory area allocated to an object, and the to-space is a portion of the memory area to which an object occupying the from-space is copied according to garbage collection. Here, the size of the to-space needs to be the same as that of the from-space because when all objects occupying the from-space are “alive”, all of the objects need to be copied to the to-space during garbage collection. In addition, to perform the conventional semi-space copying collection algorithm, two copies of a single object are temporarily needed for pointer reversal. This is disclosed by Cheney [“A Nonrecursive List Compaction Algorithm,” Communications of the ACM, 13(11), pp 677-678, 1970].
An object is an instance by which a particular class of a method or procedure of the particular class and a subclass having a data variable are implemented in object-oriented programming.
Objects are allocated to the from-space from a first stage to a third stage, as shown in FIG. 1. In the third stage, the from-space becomes full and is no longer allocated to an object. Accordingly, in a fourth stage, only “live” objects, other than objects no longer used, i.e., garbage, among the objects occupying the from-space, are copied to the to-space. As such, the previous from-space changes into to-space, and the previous to-space changes into from-space. Accordingly, in a fifth stage, objects are allocated to the from-space as in the first stage.
Usually, the semi-space copying collection algorithm is applied to another dynamic memory management algorithm, for example, a generational garbage collection algorithm, rather than be used independently.
FIG. 2 illustrates a conventional generational garbage collection algorithm.
The conventional generational garbage collection algorithm has been widely used since the 1980s. In the conventional generational garbage collection algorithm, a memory heap is divided into two or more generational spaces according to the age of an object. In FIG. 2, the memory heap is divided into a young generation area 200 and an old generation area 250. Since garbage collection is performed using a semi-space copying collection algorithm as shown in FIG. 1 in the young generation area 200, the young generation area 200 includes from-space 210 and to-space 220.
The age of an object is related to the number of copies generated of the object from one semi-space to another semi-space. Accordingly, when an object has been copied many times, the object may be regarded as being old.
Hereinafter, the conventional generational garbage collection algorithm will be described in detail.
Referring to FIG. 2, for garbage collection, a semi-space copying collection algorithm is used in the young generation area 200, and a mark-compact algorithm is used in the old generation area 250. A new object is allocated to the from-space 210, in the young generation area. Reference numerals 212, 214, 216, and 218 denote objects allocated to the from-space 210.
In the young generation area 200, garbage collection is performed by copying only live objects 212 and 216 from the from-space 210 to the to-space 220. The object 218 that has been “alive” while many garbage collections are performed in the young generation area 200 is defined as an old object and transferred to the old generation area 250.
When there is no space to which an object is transferred in the old generation area 250, garbage collection is performed in the old generation area 250 and usually takes longer than in the young generation area 200.
In the semi-space copying collection algorithm shown in FIG. 1, only one memory space between the two semi-spaces is used for object allocation. In other words, since garbage collection is performed when the memory space is full of objects, the semi-space copying collection algorithm has a problem in that the number of garbage collections increases as the size of the memory space decreases.
The generational garbage collection algorithm shown in FIG. 2 also has the above-described problem since the semi-space copying collection algorithm is usually used in the young generation area 200. In addition, the generational garbage collection algorithm has a problem in that the amount of floating garbage increases. The floating garbage indicates an object that is no longer used but still present in memory space, i.e., in the old generation area 250, because garbage collection has not yet been performed in the old generation area 250 since the object was transferred to the old generation area 250 by garbage collection performed in the young generation area 200. The more frequently garbage collection is performed, the more objects are transferred to the old generation area 250. As a result, the amount of floating garbage increases, degrading overall memory efficiency.